#include "btree.h"
#include "pcmope.h"
#include <assert.h>

#include <iostream>
using namespace std;

static void btree_split_leafnode(bt_tree * btree, bt_node * node);
static void btree_split_innernode(bt_tree * btree, short level);
static bool check_leaf_level(bt_node * node);
static short get_split_point(bt_tree * btree, bt_node * node);
static void btree_insert_leaf(bt_node * node, bt_entry * entry);
static void btree_insert_inner(bt_node * parent, bt_entry * entry, bt_node * left, bt_node * right, short level);

bt_tree * btree_create(short order)
{
	bt_tree * btree = (bt_tree *)malloc(sizeof(bt_tree));
	btree->order = order;
	btree->root = allocate_btree_node(order, (short)0);
	memset(index_trace, 0, sizeof(index_trace));
	for(short i = 0; i < MAX_TREE_LEVEL; i++)
		node_trace[i] = (bt_node *)malloc(sizeof(bt_node));
	return btree;
}

void btree_search(bt_tree * btree, bt_entry * entry, bt_entry * search_result)
{
	bt_node * node = btree->root;
	short level_index;
	for(short i = btree->root->node_level; i > 0; i--)
	{
		level_index = binary_search_greater(node->entries, node->entry_active, entry);
		node = node->children[level_index];
		index_trace[i] = level_index;
	}
	level_index = binary_search_euqal(node->entries, node->entry_active, entry);
	index_trace[0] = level_index;
	if(level_index == -1)
		search_result = NULL;
	else
	{
		search_result->key = node->entries[level_index]->key;
		search_result->value = node->entries[level_index]->value;
	}
}

void btree_insert(bt_tree * btree, bt_entry * entry)
{
	bt_node * node = btree->root;
	short level_index;
	for(short i = btree->root->node_level; i > 0; i--)
	{
		level_index = binary_search_greater(node->entries, node->entry_active, entry);
		node = node->children[level_index];
		index_trace[i] = level_index;
	}

	level_index = binary_search_greater(node->entries, node->entry_active, entry);
	index_trace[0] = level_index;

	//if(index_trace[0] >= 1 && node->entries[index_trace[0] - 1]->key == entry->key)
	//	return;

	btree_insert_leaf(node, entry);

	if(IS_NODE_FULL(btree, node))
		btree_split_leafnode(btree, node);
}

void btree_delete(bt_tree * btree, bt_entry * entry)
{
	
}

void btree_destroy(bt_tree * btree)
{

}

bool check_leaf_level(bt_node * node)
{
	if(node->node_level == 1)
	{
		for(short i = 0; i < node->entry_active + 1; i++)
		{
			if(node->children[i]->node_level != 0)
				return false;
		}
		return true;
	}
	else
	{
		bool result = true;
		for(short i = 0; i < node->entry_active + 1; i++)
			result = result && check_leaf_level(node->children[i]);
		return result;
	}
	return true;
}

bt_node * allocate_btree_node(short order, short level)
{
	bt_node * node;
	node = (bt_node *)malloc(sizeof(bt_node));
	//node->parent = NULL;
	//node->pre = NULL;
	//node->next = NULL;
	node->entry_active = 0;
	node->node_level = level;
	for (short i = 0; i < 2 * ORDER + 1; i++)
	{
		node->entries[i] = (bt_entry *)malloc(sizeof(bt_entry));
		node->children[i] = (bt_node *)malloc(sizeof(bt_node));
	}
	node->children[2 * ORDER + 1] = (bt_node *)malloc(sizeof(bt_node));
	return node;
}


void get_btree_node(bt_tree * btree, short * index)
{
	bt_node * node = btree->root;
	node_trace[node->node_level] = btree->root;
	for(short i = btree->root->node_level - 1; i >= 0; i--)
	{
		node = node->children[index[i + 1]];
		node_trace[i] = node;
	}
}

short binary_search_euqal(bt_entry ** entries, short length, bt_entry * entry)
{
	short low = 0, high = length - 1, mid;
	if (read_entry(entries[low])->key == entry->key)
		return (short)0;
	while(low <= high)
	{
		mid = (low + high) >> 1;
		bt_entry * bt_entm = read_entry(entries[mid]);
		if (bt_entm->key == entry->key)
			return mid;
		if (bt_entm->key > entry->key)
			high = mid - 1;
		else
			low = mid + 1;
	}
	return (short)-1;
}

short binary_search_greater(bt_entry ** entries, short length, bt_entry * entry)
{
	short low = 0, high = length - 1, mid;
	while(low <= high)
	{
		mid = (low + high) >> 1;
		bt_entry * bt_entm = read_entry(entries[mid]);
		if (bt_entm->key == entry->key)
		{
			short result = mid + 1;
			while(result < length && read_entry(entries[result])->key == entry->key)
				result++;
			return result;
		}
		if (bt_entm->key > entry->key)
			high = mid - 1;
		else
			low = mid + 1;
	}
}

short linear_search_greater(bt_entry ** entries, short length, bt_entry * entry)
{
	for(short i = 0; i < length; i++)
	{
		if(entries[i]->key > entry->key)
			return i;
	}
	return length;
}

void btree_insert_leaf(bt_node * node, bt_entry * entry)
{
	for(short i = node->entry_active - 1; i >= index_trace[0]; i--)
		node->entries[i + 1] = node->entries[i];
	node->entries[index_trace[0]] = entry;
	node->entry_active++;
}

void btree_insert_inner(bt_node * parent, bt_entry * entry, bt_node * left, bt_node * right, short level)
{
	short position = index_trace[level];
	for(short i = parent->entry_active; i > position; i--)
	{
		parent->entries[i] = parent->entries[i - 1];
		parent->children[i + 1] = parent->children[i];
	}
	parent->entries[position] = entry;
	parent->children[position] = left;
	parent->children[position + 1] = right;
	parent->entry_active++;
}

short get_split_point(bt_tree * btree, bt_node * node)
{
	short index = btree->order;
	for(short i = 1; i < btree->order + 1; i++)
	{
		if(read_entry(node->entries[index - i])->key != read_entry(node->entries[index])->key)
			return index - i + 1;
		if(index + i < node->entry_active && read_entry(node->entries[index + i])->key != read_entry(node->entries[index])->key)
			return index + i;
	}
	return -1;
}

void btree_split_leafnode(bt_tree * btree, bt_node * node)
{
	get_btree_node(btree, index_trace);
	short position = get_split_point(btree, node_trace[0]);
	if(position == -1)
	{
		node->entry_active--;
		return;
	}

	bt_node * newchild = allocate_btree_node(btree->order, 0);
	for(short i = position; i < 2 * btree->order + 1; i++)
		newchild->entries[i - position] = node_trace[0]->entries[i];
	node_trace[0]->entry_active = position;
	newchild->entry_active = 2 * btree->order + 1 - position;
	if(btree->root->node_level == 0)
	{
		bt_node * newroot = allocate_btree_node(btree->order, 1);
		newroot->entry_active = 1;
		newroot->entries[0] = node_trace[0]->entries[position];
		newroot->children[0] = node_trace[0];
		newroot->children[1] = newchild;
		btree->root = newroot;
	}
	else
	{
		btree_insert_inner(node_trace[1], node_trace[0]->entries[position], node_trace[0], newchild, 1);

		if(IS_NODE_FULL(btree, node_trace[1]))
			btree_split_innernode(btree, 1);
	}
}

void btree_split_innernode(bt_tree * btree, short level)
{
	short position = get_split_point(btree, node_trace[level]);
	bt_node * newchild = allocate_btree_node(btree->order, level);
	for(short i = position + 1; i < 2 * btree->order + 1; i++)
	{
		newchild->entries[i - position - 1] = node_trace[level]->entries[i];
		newchild->children[i - position - 1] = node_trace[level]->children[i];
	}
	newchild->children[2 * btree->order - position] = node_trace[level]->children[2 * btree->order + 1];

	node_trace[level]->entry_active = position;
	newchild->entry_active = 2 * btree->order - position;

	if(btree->root->node_level == level)
	{
		bt_node * newroot = allocate_btree_node(btree->order, level + 1);
		newroot->entry_active = 1;
		newroot->entries[0] = node_trace[level]->entries[position];
		newroot->children[0] = node_trace[level];
		newroot->children[1] = newchild;
		btree->root = newroot;	
	}
	else
	{
		btree_insert_inner(node_trace[level + 1], node_trace[level]->entries[position], node_trace[level], newchild, level + 1);

		if(IS_NODE_FULL(btree, node_trace[level + 1]))
			btree_split_innernode(btree, level + 1);
	}
}
